package 刷题10月.每日一题0930;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

// https://leetcode-cn.com/problems/repeated-dna-sequences/
public class 哈希和滑动或前缀和187重复的DNA序列1008 {
    class Solution {
        /*滑动窗口 + 哈希表
        数据范围只有 10^5，一个朴素的想法是：
        从左到右处理字符串 ss，使用滑动窗口得到每个以 s[i]s[i]
        为结尾且长度为 1010 的子串，同时使用哈希表记录每个子串
        的出现次数，如果该子串出现次数超过一次，则加入答案。
        为了防止相同的子串被重复添加到答案，而又不使用常数较大的 Set 结构。
        我们可以规定：当且仅当该子串在之前出现过一次
        （加上本次，当前出现次数为两次）时，将子串加入答案。
         */
        public List<String> findRepeatedDnaSequences(String s) {
            List<String> ans = new ArrayList<>();
            int n = s.length();
            Map<String, Integer> map = new HashMap<>();
            for (int i = 0; i + 10 <= n; i++) {
                String cur = s.substring(i, i + 10);
                int cnt = map.getOrDefault(cur, 0);
                if (cnt == 1) ans.add(cur);
                map.put(cur, cnt + 1);
            }
            return ans;
        }
    }

}
/*哈希表
我们可以用一个哈希表统计 ss 所有长度为 10 的子串的出现次数，返回所有出现次数超过 10的子串。
代码实现时，可以一边遍历子串一边记录答案，为了不重复记录答案，我们只统计当前出现次数为 2 的子串。
 */
/*
class Solution {
    static final int L = 10;
    public List<String> findRepeatedDnaSequences(String s) {
        List<String> ans = new ArrayList<String>();
        Map<String, Integer> cnt = new HashMap<String, Integer>();
        int n = s.length();
        for (int i = 0; i <= n - L; ++i) {
            String sub = s.substring(i, i + L);
            cnt.put(sub, cnt.getOrDefault(sub, 0) + 1);
            if (cnt.get(sub) == 2) {
                ans.add(sub);
            }
        }
        return ans;
    }
}

 */